#include "map.h"
#include<random>
#include<cmath>
#include<queue>
#include <unordered_set>
#include <QPoint>
#include <QtConcurrent/QtConcurrent>

const double PI = 3.14159265358979323846;

Map::Map(QObject* parent) : QObject(parent) {
    double cityArea = AVG_AREA / AREA_RATIO;
    cityRadius = sqrt(cityArea / PI);
}

Map::~Map() {
    for (auto v : vertices) delete v;
    for (auto e : edges) delete e;
}

//设置用户地址为地图生成的中心
void Map::setCurrentcenter(const QString& currentAddress){
    if (currentAddress.startsWith("Node")) {
        QString idStr = currentAddress.mid(4);
        bool ok;
        int id = idStr.toInt(&ok);
        if (ok) {
            QPointF pos = getVertexPosition(id);
            centerX = pos.x();
            centerY = pos.y();
        }
    }
    // 其他情况使用默认中心
    else {
        centerX = 500;
        centerY = 500;
    }

}

QPointF Map::getVertexPosition(int id) const {
    for (const Vertex* v : vertices) {
        if (v->id == id) {
            return QPointF(v->x, v->y);
        }
    }
    return QPointF(500, 500); // 默认中心（未找到时）
}

//生成随机顶点(随机的是坐标）
void Map::generateVertices(int numV){
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_real_distribution<> dis(centerX - 2000.0, centerX + 2000.0);

    std::vector<float> xValues(numV);
    std::vector<float> yValues(numV);
    for (int i = 0; i < numV; ++i) {
        xValues[i] = dis(gen);
        yValues[i] = dis(gen);
    }

    for (int i = 0; i < numV; ++i) {
        vertices.push_back(new Vertex(i, xValues[i], yValues[i], QString("Node%1").arg(i)));
    }

}

int Map::findParent(std::vector<int>& parent, int i) {
    if (parent[i] != i)
        parent[i] = findParent(parent, parent[i]);//如果没找到，继续递归找父亲的父亲
    return parent[i];
}
void Map::unionSets(std::vector<int>& parent, int x, int y) {
    parent[findParent(parent, x)] = findParent(parent, y);//使x的根为y的根的孩子
}

//通过MST添加边（连通图）
void Map:: addEdgeMST(){
    const int BLOCK_SIZE = 500; // 每块500顶点
    const int NUM_BLOCKS = vertices.size() / BLOCK_SIZE;

    std::vector<std::vector<Edge*>> blockEdges(NUM_BLOCKS);

    auto generateBlockMST = [this, &blockEdges, BLOCK_SIZE](int block) {
        int start = block * BLOCK_SIZE;
        int end = std::min((block + 1) * BLOCK_SIZE, (int)vertices.size());

        std::vector<std::pair<double, std::pair<int, int>>> localEdges;
        for (int i = start; i < end; ++i) {
            for (int j = i + 1; j < end; ++j) {
                double dx = vertices[i]->x - vertices[j]->x;
                double dy = vertices[i]->y - vertices[j]->y;
                double dist = std::hypot(dx, dy);
                localEdges.emplace_back(dist, std::make_pair(i, j));
            }
        }

        std::sort(localEdges.begin(), localEdges.end());
        std::vector<int> parent(end - start);
        std::iota(parent.begin(), parent.end(), 0);

        for (auto& edge : localEdges) {
            int u = edge.second.first - start;
            int v = edge.second.second - start;
            int rootU = findParent(parent, u);
            int rootV = findParent(parent, v);

            if (rootU != rootV) {
                blockEdges[block].push_back(
                    new Edge(vertices[edge.second.first], vertices[edge.second.second], edge.first)
                    );
                unionSets(parent, rootU, rootV);
            }
        }
    };

    QFutureSynchronizer<void> synchronizer;
    for (int block = 0; block < NUM_BLOCKS; ++block) {
        synchronizer.addFuture(QtConcurrent::run(generateBlockMST, block));
    }
    synchronizer.waitForFinished();

    // 阶段2：连接各块的边界顶点
    std::vector<std::pair<double, std::pair<int, int>>> interEdges;

    for (int srcBlock = 0; srcBlock < NUM_BLOCKS; ++srcBlock) {
        int srcStart = srcBlock * BLOCK_SIZE;
        int srcEnd = std::min((srcBlock + 1) * BLOCK_SIZE, (int)vertices.size());

        for (int dstBlock = srcBlock + 1; dstBlock < NUM_BLOCKS; ++dstBlock) {
            int dstStart = dstBlock * BLOCK_SIZE;
            int dstEnd = std::min((dstBlock + 1) * BLOCK_SIZE, (int)vertices.size());

            for (int i = srcStart; i < srcEnd; ++i) {
                for (int j = dstStart; j < dstEnd; ++j) {
                    double dist = std::hypot(
                        vertices[i]->x - vertices[j]->x,
                        vertices[i]->y - vertices[j]->y
                        );
                    interEdges.emplace_back(dist, std::make_pair(i, j));
                }
            }
        }
    }

    std::sort(interEdges.begin(), interEdges.end());
    std::vector<int> globalParent(vertices.size());
    std::iota(globalParent.begin(), globalParent.end(), 0);

    for (auto& edges : blockEdges) {
        for (auto* edge : edges) {
            this->edges.push_back(edge);
            int u = edge->start->id;
            int v = edge->end->id;
            unionSets(globalParent, u, v);
        }
    }

    for (auto& edge : interEdges) {
        int u = edge.second.first;
        int v = edge.second.second;
        int rootU = findParent(globalParent, u);
        int rootV = findParent(globalParent, v);

        if (rootU != rootV) {
            this->edges.push_back(
                new Edge(vertices[u], vertices[v], edge.first)
                );
            unionSets(globalParent, rootU, rootV);
        }
    }
}

//添加邻近边（在MST的基础上，每个最少三条）
void Map::connectEdges(int minEdgesPerVertex) {
    std::unordered_set<std::string> edgeSet;
    std::random_device rd;
    std::mt19937 gen(rd());

    // 建立 gridMap 网格索引
    const double searchGridSize = 200.0;
    std::unordered_map<std::pair<int, int>, std::vector<Vertex*>, pair_hash> gridMap;
    for (Vertex* v : vertices) {
        int gx = static_cast<int>(v->x / searchGridSize);
        int gy = static_cast<int>(v->y / searchGridSize);
        gridMap[{gx, gy}].push_back(v);
    }

    for (Vertex* v : vertices) {
        int gridX = static_cast<int>(v->x / searchGridSize);
        int gridY = static_cast<int>(v->y / searchGridSize);

        std::vector<std::pair<double, Vertex*>> nearby;

        // 搜索周围 5x5 区域（±2）
        for (int dx = -2; dx <= 2; ++dx) {
            for (int dy = -2; dy <= 2; ++dy) {
                auto key = std::make_pair(gridX + dx, gridY + dy);
                if (gridMap.count(key)) {
                    for (Vertex* u : gridMap[key]) {
                        if (u == v) continue;
                        double dist = std::hypot(v->x - u->x, v->y - u->y);
                        nearby.emplace_back(dist, u);
                    }
                }
            }
        }

        // 距离升序排序
        std::sort(nearby.begin(), nearby.end());

        // 从最近的点中选择前 minEdgesPerVertex 个未连接的
        int added = 0;
        for (const auto& [dist, u] : nearby) {
            std::string key1 = std::to_string(v->id) + "-" + std::to_string(u->id);
            std::string key2 = std::to_string(u->id) + "-" + std::to_string(v->id);

            if (edgeSet.count(key1) || edgeSet.count(key2)) continue;

            edges.push_back(new Edge(v, u, dist));
            edgeSet.insert(key1);
            added++;
            if (added >= minEdgesPerVertex) break;
        }
    }
}


void Map::buildGridIndex() {
    gridIndex.clear();
    for (Edge* edge : edges) {
        // 将边添加到其起点和终点所在的网格
        int startX = static_cast<int>(edge->start->x / gridSize);
        int startY = static_cast<int>(edge->start->y / gridSize);
        gridIndex[{startX, startY}].push_back(edge);

        int endX = static_cast<int>(edge->end->x / gridSize);
        int endY = static_cast<int>(edge->end->y / gridSize);
        if (endX != startX || endY != startY) {
            gridIndex[{endX, endY}].push_back(edge);
        }
    }
}


//生成地图
void Map::generatemap(int numVertex) {
    // 清理旧数据
    for (auto v : vertices) delete v;
    for (auto e : edges) delete e;
    vertices.clear();
    edges.clear();

    emit statusUpdate("正在生成顶点...");
    generateVertices(numVertex);
    emit statusUpdate("正在生成连通图...");
    addEdgeMST();        // 生成最小生成树确保连通
    emit statusUpdate("正在连接附近顶点...");
    connectEdges(3);     // 添加额外边（每个顶点至少3条）
    emit statusUpdate("正在建立网格索引...");
    buildGridIndex(); // 在生成地图后构建索引

    // 为每个网格分配代表点（新增逻辑）
    gridRepresentative.clear();
    for (auto* v : vertices) {
        int gridX = static_cast<int>(v->x / gridSize);
        int gridY = static_cast<int>(v->y / gridSize);
        auto gridKey = std::make_pair(gridX, gridY);
        // 每个网格选择第一个顶点作为代表点
        if (gridRepresentative.find(gridKey) == gridRepresentative.end()) {
            gridRepresentative[gridKey] = v;
        }
    }
    // map.cpp (generatemap方法末尾)
    for (auto v : vertices) {
        vertexIdMap[v->id] = v;
    }

}

// 检查线段是否交叉
bool isEdgesCrossing(double x1, double y1, double x2, double y2,
                     double x3, double y3, double x4, double y4) {
    // 计算方向向量
    double v1x = x2 - x1, v1y = y2 - y1;
    double v2x = x4 - x3, v2y = y4 - y3;

    // 计算叉积
    double cross1 = v1x * (y3 - y1) - v1y * (x3 - x1);
    double cross2 = v1x * (y4 - y1) - v1y * (x4 - x1);
    if (cross1 * cross2 >= 0) return false;

    double cross3 = v2x * (y1 - y3) - v2y * (x1 - x3);
    double cross4 = v2x * (y2 - y3) - v2y * (x2 - x3);
    return cross3 * cross4 < 0;
}

void Map::dijkstra(Vertex* source, std::unordered_map<Vertex*, double>& dist,
                   std::unordered_map<Vertex*, Edge*>& prev) {
    dist.clear();
    prev.clear();
    auto cmp = [](const std::pair<double, Vertex*>& a, const std::pair<double, Vertex*>& b) {
        return a.first > b.first;
    };
    std::priority_queue<std::pair<double, Vertex*>, std::vector<std::pair<double, Vertex*>>, decltype(cmp)> pq(cmp);

    for (auto& v : vertices) dist[v] = std::numeric_limits<double>::infinity();
    dist[source] = 0.0;
    pq.push({0.0, source});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;

        for (Edge* e : edges) {
            Vertex* v = nullptr;
            if (e->start == u) v = e->end;
            else if (e->end == u) v = e->start;
            else continue;

            double newDist = dist[u] + e->trafficTime;
            if (newDist < dist[v]) {
                dist[v] = newDist;
                prev[v] = e;
                pq.push({newDist, v});
            }
        }
    }
}

void Map::dijkstraByLength(Vertex* source,
    std::unordered_map<Vertex*, double>& dist,
    std::unordered_map<Vertex*, Edge*>& prev) {
    dist.clear();
    prev.clear();

    auto cmp = [](const std::pair<double, Vertex*>& a, const std::pair<double, Vertex*>& b) {
        return a.first > b.first;
        };
    std::priority_queue<std::pair<double, Vertex*>,
        std::vector<std::pair<double, Vertex*>>,
        decltype(cmp)> pq(cmp);

    for (auto& v : vertices) dist[v] = std::numeric_limits<double>::infinity();
    dist[source] = 0.0;
    pq.push({ 0.0, source });

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;

        for (Edge* e : edges) {
            Vertex* v = nullptr;
            if (e->start == u) v = e->end;
            else if (e->end == u) v = e->start;
            else continue;

            double newDist = dist[u] + e->length;
            if (newDist < dist[v]) {
                dist[v] = newDist;
                prev[v] = e;
                pq.push({ newDist, v });
            }
        }
    }
}

//找最近的100个点
void Map::findNear(float xx, float yy, int count) {
    showAllEdges = false; // 进入筛选模式
    visibleEdges.clear();
    currentNearVertices.clear();
    currentTarget = nullptr;

    // 查找目标点
    const float tolerance = 2.0f; // 允许2像素误差
    for (auto& v : vertices) {
        if (std::abs(v->x - xx) <= tolerance && std::abs(v->y - yy) <= tolerance) {
            currentTarget = v;
            break;
        }
    }
    if (!currentTarget) return;

    // 使用Dijkstra算法计算最短路径
    std::unordered_map<Vertex*, double> dist;
    std::unordered_map<Vertex*, Edge*> prev;
    dijkstra(currentTarget, dist, prev);

    // 按距离排序顶点
    std::vector<std::pair<double, Vertex*>> sortedDistances;
    for (auto& [v, d] : dist) {
        if (v != currentTarget) {
            sortedDistances.emplace_back(d, v);
        }
    }
    std::sort(sortedDistances.begin(), sortedDistances.end(),
              [](const auto& a, const auto& b) { return a.first < b.first; });

    // 取前count个可达顶点
    int numToTake = std::min(count, static_cast<int>(sortedDistances.size()));
    sortedDistances.resize(numToTake);

    // 收集路径上的所有边
    std::unordered_set<Edge*> pathEdges;
    for (auto& [distance, vertex] : sortedDistances) {
        Vertex* current = vertex;
        while (prev.find(current) != prev.end()) {
            Edge* edge = prev[current];
            pathEdges.insert(edge);
            current = (edge->start == current) ? edge->end : edge->start;
            if (current == currentTarget) break;
        }
    }

    // 更新可见边和顶点
    visibleEdges.assign(pathEdges.begin(), pathEdges.end());
    currentNearVertices.reserve(sortedDistances.size() + 1);
    for (auto& [d, v] : sortedDistances) {
        currentNearVertices.push_back(v);
    }
    currentNearVertices.push_back(currentTarget);
}
void Map::resetDisplay() {
    showAllEdges = true;
    visibleEdges.clear();
    currentNearVertices.clear();
    currentTarget = nullptr;
}


std::vector<Edge*> Map::findShortestPath(int startId, int endId) {
    Vertex* start = vertexIdMap.count(startId) ? vertexIdMap[startId] : nullptr;
    Vertex* end = vertexIdMap.count(endId) ? vertexIdMap[endId] : nullptr;
    // 查找起点和终点顶点
    for (auto v : vertices) {
        if (v->id == startId) start = v;
        if (v->id == endId) end = v;
    }
    if (!start || !end) return {}; // 无效ID

    // 调用Dijkstra算法计算最短路径
    std::unordered_map<Vertex*, double> dist;
    std::unordered_map<Vertex*, Edge*> prev;
    dijkstra(start, dist, prev);

    // 检查终点是否可达
    if (dist.find(end) == dist.end() || dist[end] == std::numeric_limits<double>::infinity()) {
        return {}; // 路径不存在
    }

    // 反向追踪路径
    std::vector<Edge*> path;
    Vertex* current = end;
    while (current != start) {
        if (prev.find(current) == prev.end()) break; // 防止死循环
        Edge* edge = prev[current];
        path.push_back(edge);
        current = (edge->start == current) ? edge->end : edge->start;
    }
    std::reverse(path.begin(), path.end()); // 反转路径顺序
    return path;
}

